package foundation.graph;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Dijkstra {

    static int MAXN = 101;
    static int MAXM = 6001;

    static int[] head = new int[MAXN];
    static int[] next = new int[MAXM];
    static int[] to = new int[MAXM];
    static int[] w = new int[MAXM];


    static int[] dist = new int[MAXN];
    static boolean[] visited = new boolean[MAXN];


    static int INF = Integer.MAX_VALUE;
    static int cnt;

    private static void build() {
        cnt = 1;
        Arrays.fill(head, 0);
        Arrays.fill(visited, false);
        Arrays.fill(dist, INF);
    }


    private static void add(int x, int y, int weight) {
        next[cnt] = head[x];
        to[cnt] = y;
        head[x] = cnt;
        w[cnt++] = weight;
    }

    private static void dijkstra(int s) {
        dist[s] = 0;
        // 小根堆  0 位置存储当前节点  1 位置存 源点到当前点的距离
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        heap.add(new int[]{s, 0});
        while (!heap.isEmpty()) {
            // u -> v
            int u = heap.poll()[0];
            if (!visited[u]) {
                visited[u] = true;
                for (int ei = head[u]; ei != 0; ei = next[ei]) {
                    int v = to[ei];
                    int weight = w[ei];
                    if (!visited[v] && dist[v] > dist[u] + weight) {
                        dist[v] = dist[u] + weight;
                        heap.add(new int[]{v, dist[u] + weight});
                    }
                }
            }
        }
    }


    public int networkDelayTime(int[][] times, int n, int k) {
        build();
        for (int[] time : times) {
            add(time[0], time[1], time[2]);
        }
        dijkstra(k);
        int ans = -1;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans == INF ? -1 : ans;
    }

}
